package com.jiawei.队列;

/**
 * @author : willian fu
 * @version : 1.0
 * 简单有界队列 - 数组实现 （应该用链表实现效率更高）
 * 扩容后队列元素少的话应该动态减少容量，这里没加
 */
public class SimpleArrayQueue<E> implements Queue<E>{

    //最大队列长度
    private static final int MAX_SIZE = Integer.MAX_VALUE;

    //初始长度
    private static final int INIT_SIZE = 10;

    //扩容因子
    private static final double EXPAND = 0.5;

    private int length;
    //数据
    private Object[] queue;

    public SimpleArrayQueue() {
        this.queue = new Object[INIT_SIZE];
    }

    public SimpleArrayQueue(int capacity) {
        this.queue = new Object[capacity];
    }
    /**
     * 获取队列头部元素，获取后会删除该元素
     *
     * @return 值
     */
    @Override
    public E get() {
        Object data = this.queue[0];
        //数据前移一位 这个操作比较低效，应该换成链表
        for (int i = 0; i < this.length && i < this.queue.length - 1; i++) {
            this.queue[i] = this.queue[i + 1];
        }
        this.queue[this.length - 1] = null;
        this.length--;
        return (E) data;
    }

    /**
     * 添加一个元素到队列
     *
     * @param val 值
     * @return 添加结果
     */
    @Override
    public boolean add(E val) {
        if (this.queue.length <= this.length){
            expandSpace();
        }
        this.queue[this.length] = val;
        this.length++;
        return true;
    }

    /**
     * 获取队列长度
     *
     * @return 长度
     */
    @Override
    public int length() {
        return this.length;
    }

    @Override
    public void print() {
        System.out.print("\n => ");
        for (int i = 0; i < this.length; i++) {
            System.out.print(" - " + this.queue[i]);
        }
        System.out.print("\n");
    }

    /**
     * 扩容
     */
    private void expandSpace() {
        if (this.queue.length == MAX_SIZE) {
            throw new RuntimeException("队列容量已到极限");
        }
        int afterSize = this.queue.length + (int) (this.queue.length * EXPAND);
        //限制最大容量
        if (afterSize > MAX_SIZE) {
            afterSize = MAX_SIZE;
        }
        Object[] object = new Object[afterSize];
        System.arraycopy(this.queue, 0, object, 0, this.length);
        this.queue = object;
    }
}
